package cn.suchan.jianzhi.q41_sequence;

import java.util.ArrayList;
import java.util.TreeSet;

/**
 * 知识点：和为s的连续正数序列
 * 题目描述
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
 * 但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
 * 没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
 * 现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 * 输出描述:
 * 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
 *
 * @author suchan
 * @date 2019/06/04
 */
public class Solution {

    /**
     * 题目中要求的连续正整数序列，即为一个公差d为1的等差数列；
     * 而所要返回的序列之和S则为等差数列的前n项和。
     * <p>
     * 求等差数列前n项和数学公式如下：
     * # ① Sn = (n * (a1 + an)) / 2;
     * # ② Sn = (d / 2) * n^2 + (a1 - (d / 2)) * n;
     * </p>
     * <p>
     * 由①式简化可得：
     * # ③ a1 = (2 * Sn - n * an) / n;
     * </p>
     * <p>
     * 由②式简化可得：
     * # ④ an = (Sn - (d / 2) * n + (d / 2) * n^2) / n;
     * </p>
     * <p>
     * 已知公差d=1，则有：
     * # ⑤ an = (2 * Sn - n + n^2) / 2 * n;
     * </p>
     * <p>
     * 由③式和④式化简可得：
     * # ⑥ a1 = (Sn + (d / 2) * n - (d / 2) * n^2) / n;
     * </p>
     * <p>
     * 已知公差d=1，则有：
     * # ⑦ a1 = (2 * Sn + n - n^2) / 2 * n;
     * </p>
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        // 前n项和必须大于等于3，因为项数n必须大于等于2
        if (sum < 3) {
            return resultList;
        }

        // 由①式可得：n * (a1 + an) = 2 * Sn；
        // 由题可知，项数n满足：n >= 2；序列a1和an满足：a1 + an >= 3；则有：a1 + an > n；
        // 由上述条件可得：n^2 < 2 * Sn，即：n = sqrt(2 * Sn)
        // 由于需要序列中元素按照a1从小到大排序，所以使用n递减的方式进行循环（Sn不变，项数n越大，数列元素值越小）
        for (int n = Double.valueOf(Math.sqrt(sum * 2)).intValue(); n >= 2; n--) {
            // 由⑤式和⑦式可得：
            int a1 = (2 * sum + n - n * n) / (2 * n);
            int an = (2 * sum - n + n * n) / (2 * n);

            // 由①式可得：
            int tempSn = (n * (a1 + an)) / 2;
            // 判断已知a1、an，由①式求得的前n项（n为循环参数）和tempSn是否等于所要求的sum
            // 要求数列中所有元素值均为正整数
            if (tempSn == sum && a1 > 0 && an > 0) {
                ArrayList<Integer> sn = new ArrayList<>();
                while (a1 <= an) {
                    sn.add(a1);
                    a1++;
                }
                resultList.add(sn);
            }
        }
        return resultList;
    }

    /**
     * 由上述①式化简可得关于n的一元二次方程如下：
     * # ⑧ d * n^2 + (2 * a1 - d) * n - 2 * Sn = 0;
     * 已知公差d=1，则有：
     * # ⑨ n^2 + (2 * a1 - 1) * n - 2 * Sn = 0;
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence1(int sum) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        // 前n项和必须大于等于3，因为项数n必须大于等于2
        if (sum < 3) {
            return resultList;
        }

        // 由⑨式可得：
        int a = 1;
        int b = 0;
        int c = -2 * sum;

        // 由经验可得：an >= Sn/2（向上取整）; a1 <= an
        double mid = Math.ceil(sum / 2.0);
        for (int a1 = 1; a1 <= mid; a1++) {
            // 已知a1和Sn,对⑨式进行求解（解一元二次方程）
            b = 2 * a1 - 1;
            // b^2-4ac
            int temp = b * b - (4 * a * c);
            if (temp > 0) {
                int n1 = Double.valueOf((-b + Math.sqrt(temp)) / 2 * a).intValue();
                int n2 = Double.valueOf((-b - Math.sqrt(temp)) / 2 * a).intValue();
                if (n1 > 0) {
                    getSn(n1, a1, sum, resultList);
                }
                if (n2 > 0) {
                    getSn(n2, a1, sum, resultList);
                }
            } else if (temp == 0) {
                int n3 = Double.valueOf((Math.sqrt(temp) - b) * 1.0 / (2 * a)).intValue();
                getSn(n3, a1, sum, resultList);
            }
        }

        return resultList;
    }

    private void getSn(int n, int a1, int Sn, ArrayList<ArrayList<Integer>> resultList) {
        // 由②式可得：
        double tempSn = (n * n) / 2 + a1 * n - n / 2;
        if (tempSn == Sn) {
            int tempA1 = a1;
            int i = 1;
            ArrayList<Integer> sn = new ArrayList<>();
            while (i <= n) {
                sn.add(tempA1);
                tempA1++;
                i++;
            }
            resultList.add(sn);
        }
    }

    /**
     * 这次使用中位数的方式进行实现
     *
     * <p>
     * ① n = 2k + 1时（奇数），S / n 的结果（整个序列的平均数）恰好为序列的中位数（中间位置的数）。
     * 举例：现有S = 100，有连续奇数序列：{18,19,20,21,22}，
     * 可以看出：n = 5，S / n = 100 / 5 = 20。
     * ② n = 2k时（偶数），项数n = S % n * 2；S / n 的结果是中间两项左边的那项的值。
     * 举例：现有S = 100，有连续偶数序列：{9,10,11,12,13,14,15,16}，
     * 可以看出：n = 8，S / n = 100 / 8 = 12；而项数n= S % n * 2 = 100 % 8 * 2 = 8。
     * ③ 和为S，项数为n，如何写出这个序列？  由⑤式可得：a1 = S / n - ((n-1) / 2) 
     * 解读：执行的除法是地板除法（floor），即向下取整。
     * 仍使用上述例子，100 / 8 = 12，12恰好是中间项左边的那一项；12 - ((8 - 1) / 2 ) = 9，恰好是序列最左端。
     * </p>
     *
     * @param sum
     * @return
     */
    public ArrayList<ArrayList<Integer>> FindContinuousSequence2(int sum) {
        ArrayList<ArrayList<Integer>> resultList = new ArrayList<>();
        // 前n项和必须大于等于3，因为项数n必须大于等于2
        if (sum < 3) {
            return resultList;
        }
        // 由①式可得：n * (a1 + an) = 2 * Sn；
        // 由题可知，项数n满足：n >= 2；序列a1和an满足：a1 + an >= 3；则有：a1 + an > n；
        // 由上述条件可得：n^2 < 2 * Sn，即：n = sqrt(2 * Sn)
        // 由于需要序列中元素按照a1从小到大排序，所以使用n递减的方式进行循环（Sn不变，项数n越大，数列元素值越小）
        for (int n = Double.valueOf(Math.sqrt(sum * 2)).intValue(); n >= 2; n--) {
            // 奇偶数的判定方法除了n%2==0之外，还可以使用与运算的特性，即：奇数&1=1；偶数&1=0
            if (n % 2 == 0) {
                // 若n为偶数
                if (n == (sum % n) * 2) {
                    // 求出序列中，中间两项的左边项的值
                    int mid = sum / n;

                    ArrayList<Integer> sn = new ArrayList<>();
                    // 中间两项中左边项的位数（从1开始算）
                    /*int midIndex = n / 2;
                    sn.set(midIndex, mid);*/

                    TreeSet<Integer> treeSet = new TreeSet<>();
                    treeSet.add(mid);

                    // 中间两项中左边项的左右两边的个数
                    int left = (n / 2) - 1;
                    int right = n / 2;

                    int leftVal = mid;
                    int rightVal = mid;
                    // 因为右边的个数比左边多一个，所以用右边来做条件
                    while (right > 0) {
                        if (left > 0) {
                            treeSet.add(--leftVal);
                            left--;
                        }
                        treeSet.add(++rightVal);
                        right--;
                    }
                    sn.addAll(treeSet);
                    resultList.add(sn);
                }
            } else {
                // 若n为奇数
                // 求出序列的中位数（中间项的值）
                int mid = sum / n;
                if (mid > 0) {
                    // 序列中位数左右两边的个数
                    int count = (n - 1) / 2;
                    int temp = 1;


                    ArrayList<Integer> sn = new ArrayList<>();
                    /*int midIndex = (n + 1) / 2;
                    sn.set(midIndex, mid);*/
                    TreeSet<Integer> treeSet = new TreeSet<>();
                    treeSet.add(mid);

                    int leftVal = mid;
                    int rightVal = mid;
                    while (temp <= count) {
                        treeSet.add(--leftVal);
                        treeSet.add(++rightVal);
                        temp++;
                    }
                    sn.addAll(treeSet);
                    resultList.add(sn);
                }
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ArrayList<ArrayList<Integer>> resultList = solution.FindContinuousSequence2(9);
        resultList.forEach(result -> System.out.println(result));
    }
}
